﻿// --------------------------------------------------------------------------------------------------------------------
// <copyright file="Geni.cs" company="Luis de la Torre">
//   Copyright Luis de la Torre, unless otherwise indicated
// </copyright>
// <summary>
//   Defines the Geni type.
// </summary>
// --------------------------------------------------------------------------------------------------------------------
namespace PVRP_SR
{
    using System;
    using System.Collections.Generic;
    using System.Diagnostics;
    using System.Diagnostics.CodeAnalysis;

    /// <summary>
    /// The geni insertion class.
    /// </summary>
    public class Geni : ImprovementHeuristic
    {
        // NeighborsSorted[i][j] is the jth closest closest node to node i
        #region Fields

        /// <summary>
        /// The moves.
        /// </summary>
        [SuppressMessage("StyleCop.CSharp.MaintainabilityRules", "SA1401:FieldsMustBePrivate", 
            Justification = "Reviewed. Suppression is OK here.")]
        public List<PvrpSrMove> Moves;

        /// <summary>
        /// The neighborhood size.
        /// </summary>
        private readonly int neighborhoodSize; // the value p of the p-neighborhood in the geni heuristic

        #endregion

        #region Constructors and Destructors

        /// <summary>
        /// Initializes a new instance of the <see cref="Geni"/> class.
        /// </summary>
        /// <param name="solution">
        /// The solution.
        /// </param>
        /// <param name="neighborhoodSize">
        /// The neighborhood size.
        /// </param>
        public Geni(PvrpSrSolution solution, int neighborhoodSize)
        {
            this.Moves = new List<PvrpSrMove>();

            int numNodes = solution.Instance.NumNodesRegular + solution.Instance.StartDepots.Length;

            int[] nodeIndices = new int[numNodes];

            // the node indices include all regular nodes, plus the start depot
            for (int i = 0; i <= solution.Instance.NumNodesRegular; i++)
            {
                nodeIndices[i] = i;
            }

            this.NeighborsSorted = new Dictionary<int, int[]>();
            foreach (int i in nodeIndices)
            {
                this.NeighborsSorted[i] = new int[numNodes];
                foreach (int node in nodeIndices)
                {
                    this.NeighborsSorted[i][node] = node;
                }

                Array.Sort(this.NeighborsSorted[i], new CmpDistToI(solution.Instance.Distances[i]));
            }

            this.neighborhoodSize = neighborhoodSize;
            this.PNeighborhood = new int[solution.Instance.NumDays][][][];
            for (int i = 0; i < this.PNeighborhood.Length; i++)
            {
                this.PNeighborhood[i] = new int[solution.Instance.NumVehicles][][];
                for (int j = 0; j < this.PNeighborhood[0].Length; j++)
                {
                    this.PNeighborhood[i][j] = new int[solution.Instance.NumNodesRegular][];
                    for (int k = 0; k < this.PNeighborhood[0][0].Length; k++)
                    {
                        this.PNeighborhood[i][j][k] = new int[this.neighborhoodSize];
                    }
                }
            }
        }

        #endregion

        #region Public Properties

        /// <summary>
        /// Gets the neighbors sorted.
        /// </summary>
        public Dictionary<int, int[]> NeighborsSorted { get; private set; }

        /// <summary>
        /// Gets the p neighborhood.
        /// </summary>
        public int[][][][] PNeighborhood { get; private set; }

        #endregion

        #region Public Methods and Operators

        /// <summary>
        /// The improve solution.
        /// </summary>
        /// <param name="solution">
        /// The solution.
        /// </param>
        public override void ImproveSolution(PvrpSrSolution solution)
        {
            foreach (PvrpSrMove move in this.Moves)
            {
                this.Insert(solution, move.Node, move.NewVehicle);
            }
        }

        #endregion

        ///// <summary>
        ///// The p neighborhood for a set of vertices is the is the set of p vertices on the tour closest to vertex v
        ///// This function may not be needed, since we just need to look through the list of sorted neighbors and find the closest...
        ///// </summary>
        // private void InitializePNeighborhoods(PvrpSrSolution solution)
        // {
        // //initialize the p-neighborhoods to be nothing for all nodes
        // //for(int t = 0; t < solution.Instance.NumDays; t++)
        // //{
        // //    for (int v = 0; v < solution.Instance.NumVehicles; v++)
        // //    {
        // //        for (int i = 0; i < solution.Instance.NumNodesRegular; i++)
        // //        {
        // //            for (int j = 0; j < neighborhoodSize; j++)
        // //            {
        // //                PNeighborhood[t, v, i, j] = -1;
        // //            }
        // //        }
        // //    }
        // //}

        // //calculate the p-neighborhood on each day in each route
        // for(int t = 0; t < solution.Instance.NumDays; t++)
        // {
        // for(int k = 0; k < solution.Instance.NumVehicles; k++)
        // {
        // for (int i = 0; i < solution.Instance.NumNodesRegular; i++)
        // {
        // //there should always be at least two nodes on the route, the start and end depot
        // //assume start and end depot are the same, so this counts as only one node
        // //if each node has less than p neighbors on the tour, all neighbors are on the tour
        // int p = 0;
        // int i1 = i;
        // foreach (int node in solution.Routes[t, k].Nodes.Where(node => node != solution.Instance.EndDepots[0] && node != i1))
        // {
        // PNeighborhood[t][k][i][p++] = node;
        // }
        // //if there are more than P nodes in the neighborhood, sort them
        // if (solution.Routes[t, k].Nodes.Count > neighborhoodSize + 2)
        // {
        // CmpDistToI cmp = new CmpDistToI(solution.Instance.Distances[i]);
        // Array.Sort(PNeighborhood[t][k][i], cmp);

        // //List<KeyValuePair<int, double>> nodesSorted = new List<KeyValuePair<int, double>>(solution.Instance.NumNodesRegular);
        // //nodesSorted.AddRange(solution.Routes[t, k].Nodes.Where(node2 => node2 != node && node2 != solution.Instance.EndDepots[0]).Select(node2 => new KeyValuePair<int, double>(node2, solution.Instance.Distances[node, node2])));
        // //nodesSorted = (from kv in nodesSorted orderby kv.Value ascending select kv).ToList();
        // //for (int i = 0; i < neighborhoodSize; i++)
        // //{
        // //    PNeighborhood[t, node, i] = nodesSorted.ElementAt(i).Key;
        // //}

        // }
        // }
        // }
        // }
        // }
        #region Methods

        /// <summary>
        /// The sub path.
        /// </summary>
        /// <param name="solution">
        /// The solution.
        /// </param>
        /// <param name="day">
        /// The day.
        /// </param>
        /// <param name="vehicle">
        /// The vehicle.
        /// </param>
        /// <param name="v1">
        /// The v 1.
        /// </param>
        /// <param name="v2">
        /// The v 2.
        /// </param>
        /// <returns>
        /// Returns a sub-path
        /// </returns>
        private static List<int> SubPath(PvrpSrSolution solution, int day, int vehicle, int v1, int v2)
        {
            List<int> subPath = new List<int>();

            for (int i = v1; i != solution.Successors[day][vehicle][v2]; i = solution.Successors[day][vehicle][i])
            {
                subPath.Add(i);
            }

            return subPath;
        }

        /// <summary>
        /// The insert.
        /// </summary>
        /// <param name="solution">
        /// The solution.
        /// </param>
        /// <param name="v">
        /// The v.
        /// </param>
        /// <param name="vehicle">
        /// The vehicle.
        /// </param>
        private void Insert(PvrpSrSolution solution, int v, int vehicle)
        {
#if DEBUG
            for (int t = 0; t < solution.Instance.NumDays; t++)
            {
                if (solution.Instance.Demands[t][v] >= 0)
                {
                    Debug.Assert(solution.IsRouted(t, v), "node must be routed on days it has demand");
                }

                Debug.Assert(
                    !solution.Routes[t, vehicle].Nodes.Contains(v), 
                    "error - trying to move node to vehicle it is already assigned");
            }

#endif

            // the best cost for each day
            double[] bestCosts = new double[solution.Instance.NumDays];
            for (int i = 0; i < bestCosts.Length; i++)
            {
                bestCosts[i] = double.PositiveInfinity;
            }

            // the best insertion points for each day
            // vi
            // vj
            // vk
            // insertion type: 1 if if type 1, 2 if type 2
            // orientation: 1 if orientation is vi -> vj, -1 if orientation is vi <- vj (reversed)
            int[] bestVi = new int[solution.Instance.NumDays];
            int[] bestVj = new int[solution.Instance.NumDays];
            int[] bestVk = new int[solution.Instance.NumDays];
            int[] bestVl = new int[solution.Instance.NumDays];
            int[] bestInsertionType = new int[solution.Instance.NumDays];
            int[] bestOrientation = new int[solution.Instance.NumDays];

            // consider insertion points vi != vj, in N_p(v), v_k in N_p(v_i+1), v_l in N_p(v_j+1)
            for (int t = 0; t < solution.Instance.NumDays; t++)
            {
                // loop through vi, vj in route, vi comes before vj in the route
                for (int i = 0; i < solution.Routes[t, vehicle].Nodes.Count; i++)
                {
                    int vi = solution.Routes[t, vehicle].Nodes[i];
                    for (int j = i + 1; j < solution.Routes[t, vehicle].Nodes.Count; j++)
                    {
                        int vj = solution.Routes[t, vehicle].Nodes[j];
                        bool viInNeighborhood = false;
                        bool vjInNeighborhood = false;
                        bool neighborhoodSearched = false;
                        int p = 0;
                        foreach (int neighb in this.NeighborsSorted[v])
                        {
                            if (solution.Routes[t, vehicle].Nodes.Contains(neighb))
                            {
                                p++;
                                if (p <= this.neighborhoodSize)
                                {
                                    if (vi == neighb)
                                    {
                                        viInNeighborhood = true;
                                    }

                                    if (vj == neighb)
                                    {
                                        vjInNeighborhood = true;
                                    }
                                }
                                else
                                {
                                    neighborhoodSearched = true;
                                }
                            }

                            if (neighborhoodSearched)
                            {
                                break;
                            }
                        }

                        // if vi and vj are in the p-neighboorhood of v, look for vk in N_p(v_i+1) and vl in N_p(v_j+1)
                        // vk is on the route from vi to vj, and vl is on the route from vj to vi
                        if (!viInNeighborhood || !vjInNeighborhood)
                        {
                            continue;
                        }

                        // vk is between vj and vi in the route
                        // in terms of route indices, since vj comes after vi, the index of k is at least j
                        for (int k = j; k < solution.Routes[t, vehicle].Nodes.Count; k++)
                        {
                            int vk = solution.Routes[t, vehicle].Nodes[k];

                            // check if vk is in the neighborhood of vi+1
                            bool vkInNeighborhood = false;
                            bool kNeighborhoodSearched = false;
                            int pkPos = 0;


                            // successors on the positive and negative orientation of the route
                            int viPlusOnePos = solution.Successors[t][vehicle][vi];
                            int vjPlusOnePos = solution.Successors[t][vehicle][vj];
                            int vkPlusOnePos = solution.Successors[t][vehicle][vk];

                            int viPlusOneNeg = solution.Predecessors[t][vehicle][vi];
                            int vjPlusOneNeg = solution.Predecessors[t][vehicle][vj];
                            int vkPlusOneNeg = solution.Predecessors[t][vehicle][vk];

                            //check if vk is in the 
                            foreach (int neighb in this.NeighborsSorted[viPlusOnePos])
                            {
                                if (solution.Routes[t, vehicle].Nodes.Contains(neighb))
                                {
                                    pkPos++;
                                    if (pkPos <= this.neighborhoodSize)
                                    {
                                        if (vk == neighb)
                                        {
                                            vkInNeighborhood = true;
                                        }
                                    }
                                    else
                                    {
                                        kNeighborhoodSearched = true;
                                    }
                                }

                                if (kNeighborhoodSearched)
                                {
                                    break;
                                }
                            }

                            if (!vkInNeighborhood)
                            {
                                continue;
                            }

                            // check the cost of type I insertion for this vi, vj and vk
                            // vk != vi and vk != vj
                            if (vk != vi && vk != vj)
                            {
                                double insertionCost = 0;

                                // removed arcs
                                insertionCost -= solution.Instance.Distances[vi][viPlusOnePos]
                                                 + solution.Instance.Distances[vj][vjPlusOnePos]
                                                 + solution.Instance.Distances[vk][vkPlusOnePos];

                                // added arcs
                                insertionCost += solution.Instance.Distances[vi][v] + solution.Instance.Distances[v][vj]
                                                 + solution.Instance.Distances[viPlusOnePos][vk]
                                                 + solution.Instance.Distances[vjPlusOnePos][vkPlusOnePos];
                                if (insertionCost < bestCosts[t])
                                {
                                    bestCosts[t] = insertionCost;
                                    bestVi[t] = vi;
                                    bestVj[t] = vj;
                                    bestVk[t] = vk;
                                    bestInsertionType[t] = 1;
                                    bestOrientation[t] = 1;
                                }
                            }

                            // vl is between vi and vj in the route
                            // in terms of route indices, since vi comes before vj, the index of l runs from i to j, inclusive
                            for (int l = i; l <= j; l++)
                            {
                                int vl = solution.Routes[t, vehicle].Nodes[l];
                                int vlPlusOnePos = solution.Successors[t][vehicle][vl];
                                int vlPlusOneNeg = solution.Predecessors[t][vehicle][vl];

                                bool vlInNeighborhood = false;
                                bool lNeighborhoodSearched = false;

                                int pl = 0;

                                foreach (int neighb in this.NeighborsSorted[vjPlusOnePos])
                                {
                                    if (solution.Routes[t, vehicle].Nodes.Contains(neighb))
                                    {
                                        pl++;
                                        if (pl <= this.neighborhoodSize)
                                        {
                                            if (vl == neighb)
                                            {
                                                vlInNeighborhood = true;
                                            }
                                        }
                                        else
                                        {
                                            lNeighborhoodSearched = true;
                                        }
                                    }

                                    if (lNeighborhoodSearched)
                                    {
                                        break;
                                    }
                                }

                                if (!vlInNeighborhood)
                                {
                                    continue;
                                }

                                // check the conditions for a type II insertion
                                if (vk == vj || vk == vjPlusOnePos || vl == vi || vl == vlPlusOnePos)
                                {
                                    continue;
                                }

                                double insertionCost = 0;

                                int vkMinusOne = solution.Predecessors[t][vehicle][vk];
                                int vlMinusOne = solution.Predecessors[t][vehicle][vl];

                                // removed arcs
                                insertionCost -= solution.Instance.Distances[vi][viPlusOnePos]
                                                 + solution.Instance.Distances[vlMinusOne][vl]
                                                 + solution.Instance.Distances[vj][vjPlusOnePos]
                                                 + solution.Instance.Distances[vkMinusOne][vk];

                                // added arcs
                                insertionCost += solution.Instance.Distances[vi][v] + solution.Instance.Distances[v][vj]
                                                 + solution.Instance.Distances[vl][vjPlusOnePos]
                                                 + solution.Instance.Distances[vkMinusOne][vlMinusOne]
                                                 + solution.Instance.Distances[viPlusOnePos][vk];

                                // Skip!
                                if (!(insertionCost < bestCosts[t]))
                                {
                                    continue;
                                }

                                bestCosts[t] = insertionCost;
                                bestVi[t] = vi;
                                bestVj[t] = vj;
                                bestVk[t] = vk;
                                bestVl[t] = vl;
                                bestInsertionType[t] = 2;
                                bestOrientation[t] = 1;
                            }
                        }
                    }
                }
            }
        }

        // <summary>
        // This is a type one geni insertion
        // The node names v, vi, vj, vk, and vl are not descriptive, but there are not good names for them!
        // </summary>
        // <param name="solution">
        // </param>

        /// <summary>
        /// The type one insertion.
        /// </summary>
        /// <param name="solution">
        /// The solution.
        /// </param>
        /// <param name="day">
        /// </param>
        /// <param name="vehicle">
        /// The vehicle.
        /// </param>
        /// <param name="v">
        /// the vertex to insert
        /// </param>
        /// <param name="vi">
        /// </param>
        /// <param name="vj">
        /// </param>
        /// <param name="vk">
        /// a chosen vertex along the path from vj to vi
        /// </param>
        /// <returns>
        /// The <see cref="Path"/>.
        /// </returns>
        [SuppressMessage("StyleCop.CSharp.DocumentationRules", "SA1650:ElementDocumentationMustBeSpelledCorrectly", 
            Justification = "Reviewed. Suppression is OK here.")]
        private Path TypeOneInsertion(PvrpSrSolution solution, int day, int vehicle, int v, int vi, int vj, int vk)
        {
            Debug.Assert(vk != vi, "vk should not be equal to vi");
            Debug.Assert(vk != vj, "vk should not be equal to vj");

            Path path = new Path(solution.Routes[day, vehicle]);

            // new order of arcs: v_i, v, v_j
            int viPlusOne = solution.Successors[day][vehicle][vi];
            int vjPlusOne = solution.Successors[day][vehicle][vj];
            int vkPlusOne = solution.Successors[day][vehicle][vk];

            List<int> subPath1 = SubPath(solution, day, vehicle, viPlusOne, vj);
            List<int> subPath2 = SubPath(solution, day, vehicle, vjPlusOne, vk);
            subPath1.Reverse();
            subPath2.Reverse();

            int viRouteIdx = solution.Routes[day, vehicle].Nodes.IndexOf(vi);
            int vjRouteIdx = solution.Routes[day, vehicle].Nodes.IndexOf(vj);
            int vkRouteIdx = solution.Routes[day, vehicle].Nodes.IndexOf(vk);

#if DEBUG
            path.PrintPath();
#endif

            // after this adjustment, route is vi, v, vi+1, p1,...,pn,vj,...
            path.Nodes.Insert(v, viRouteIdx - 1);

#if DEBUG
            path.PrintPath();
#endif

            // after this adjustment, route is vi, v, vj+1,...
            path.Nodes.RemoveRange(viRouteIdx + 1, vjRouteIdx - viRouteIdx + 1);
#if DEBUG
            path.PrintPath();
#endif

            // after this adjustment, route is vi, v, vj, pn,..., p1, vi+1, vj+1,q1,...,qn, vk
            path.Nodes.InsertRange(viRouteIdx + 1, subPath1);
#if DEBUG
            path.PrintPath();
#endif

            // after this adjustment, route is vi, v, vj, pn,..., p1, vi+1
            path.Nodes.RemoveRange(vjRouteIdx + 1, vkRouteIdx - vjRouteIdx + 1);
#if DEBUG
            path.PrintPath();
#endif

            // after this adjustment, route is vi, v, vj, pn,..., p1, vi+1, vk, qn, ..., q1, vj+1
            path.Nodes.InsertRange(vjRouteIdx + 1, subPath2);
#if DEBUG
            path.PrintPath();
#endif

            // redo successors and predecessors
            // hold off on this until solution is actualy modified
            // int top = solution.Routes[day, vehicle].Nodes.IndexOf(vkPlusOne) + 1;
            // for (int i = solution.Routes[day, vehicle].Nodes.IndexOf(vi);
            // i < top; i++)
            // {
            // int node = solution.Routes[day, vehicle].Nodes.ElementAt(i);
            // int next = solution.Routes[day, vehicle].Nodes.ElementAt((i + 1));

            // solution.Successors[day, vehicle, node] = next;
            // solution.Predecessors[day, vehicle, next] = node;                
            // }
            return path;
        }

        // <summary>
        // The type two insertion.
        // </summary>
        // <param name="solution">
        // The solution.
        // </param>
        /// <summary>
        /// The type two insertion.
        /// </summary>
        /// <param name="solution">
        /// The solution.
        /// </param>
        /// <param name="day">
        /// The day.
        /// </param>
        /// <param name="vehicle">
        /// The vehicle.
        /// </param>
        /// <param name="v">
        /// The v.
        /// </param>
        /// <param name="vi">
        /// The vi.
        /// </param>
        /// <param name="vj">
        /// The vj.
        /// </param>
        /// <param name="vk">
        /// The vk.
        /// </param>
        /// <param name="vl">
        /// The vl.
        /// </param>
        /// <returns>
        /// The <see cref="Path"/>.
        /// </returns>
        [SuppressMessage("StyleCop.CSharp.DocumentationRules", "SA1650:ElementDocumentationMustBeSpelledCorrectly", 
            Justification = "Reviewed. Suppression is OK here.")]
        private Path TypeTwoInsertion(
            PvrpSrSolution solution, int day, int vehicle, int v, int vi, int vj, int vk, int vl)
        {
            Path path = new Path(solution.Routes[day, vehicle]);

            int viPlusOne = solution.Successors[day][vehicle][vi];
            int vlMinusOne = solution.Predecessors[day][vehicle][vl];

            List<int> subPathlToj = SubPath(solution, day, vehicle, vl, vj);
            List<int> subPathiTol = SubPath(solution, day, vehicle, viPlusOne, vlMinusOne);

            subPathlToj.Reverse();
            subPathiTol.Reverse();

            int viRouteIdx = solution.Routes[day, vehicle].Nodes.IndexOf(vi);

            // infer the index of j from the routes and the length of the subpaths between them (no lookup required)
            int vjRouteIdx = viRouteIdx + 1 + subPathlToj.Count + subPathiTol.Count;
            int vkRouteIdx = solution.Routes[day, vehicle].Nodes.IndexOf(vk);

            // vi, v, vi+1, q1,...,qn, vl-1, vl1, p1,...,pn,vj,vj+1,...,vk-1,vk,...,vi
            path.Nodes.Insert(v, viRouteIdx - 1);

#if DEBUG
            path.PrintPath();
#endif

            // remove vi+1, q1,...,qn, vl-1, vl, p1,...,pn, vj
            path.Nodes.RemoveRange(viRouteIdx + 1, vjRouteIdx);

#if DEBUG
            path.PrintPath();
#endif

            // insert vj to vl
            path.Nodes.InsertRange(viRouteIdx + 1, subPathlToj);

#if DEBUG
            path.PrintPath();
#endif

            // insert second subpath
            path.Nodes.InsertRange(vkRouteIdx - 1, subPathiTol);

#if DEBUG
            path.PrintPath();
#endif

            return path;
        }

        #endregion
    }
}